{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chap5 Array-Based Sequences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:10.312742Z",
     "start_time": "2019-07-15T02:05:09.473913Z"
    }
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "import pandas as pd\n",
    "import random\n",
    "from time import time\n",
    "import ctypes\n",
    "from typing import List, TypeVar\n",
    "Num = TypeVar('Num', int, float)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Reinforcement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### R-5.1\n",
    "Execute the experiment from Code Fragment 5.1 and compare the results\n",
    "on your system to those we report in Code Fragment 5.2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:10.320357Z",
     "start_time": "2019-07-15T02:05:10.315262Z"
    }
   },
   "outputs": [],
   "source": [
    "def test_array_1(n=27):\n",
    "    data = []\n",
    "    for _ in range(n):\n",
    "        a = len(data)\n",
    "        b = sys.getsizeof(data)\n",
    "        print('Length: {0:3d}; Size in bytes: {1:4d}'.format(a, b))\n",
    "        data.append(None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:10.468203Z",
     "start_time": "2019-07-15T02:05:10.323048Z"
    },
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length:   0; Size in bytes:   64\n",
      "Length:   1; Size in bytes:   96\n",
      "Length:   2; Size in bytes:   96\n",
      "Length:   3; Size in bytes:   96\n",
      "Length:   4; Size in bytes:   96\n",
      "Length:   5; Size in bytes:  128\n",
      "Length:   6; Size in bytes:  128\n",
      "Length:   7; Size in bytes:  128\n",
      "Length:   8; Size in bytes:  128\n",
      "Length:   9; Size in bytes:  192\n",
      "Length:  10; Size in bytes:  192\n",
      "Length:  11; Size in bytes:  192\n",
      "Length:  12; Size in bytes:  192\n",
      "Length:  13; Size in bytes:  192\n",
      "Length:  14; Size in bytes:  192\n",
      "Length:  15; Size in bytes:  192\n",
      "Length:  16; Size in bytes:  192\n",
      "Length:  17; Size in bytes:  264\n",
      "Length:  18; Size in bytes:  264\n",
      "Length:  19; Size in bytes:  264\n",
      "Length:  20; Size in bytes:  264\n",
      "Length:  21; Size in bytes:  264\n",
      "Length:  22; Size in bytes:  264\n",
      "Length:  23; Size in bytes:  264\n",
      "Length:  24; Size in bytes:  264\n",
      "Length:  25; Size in bytes:  264\n",
      "Length:  26; Size in bytes:  344\n"
     ]
    }
   ],
   "source": [
    "test_array_1()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### R-5.2\n",
    "In Code Fragment 5.1, we perform an experiment to compare the length of\n",
    "a Python list to its underlying memory usage. Determining the sequence\n",
    "of array sizes requires a manual inspection of the output of that program.\n",
    "Redesign the experiment so that the program outputs only those values of\n",
    "k at which the existing capacity is exhausted. For example, on a system\n",
    "consistent with the results of Code Fragment 5.2, your program should\n",
    "output that the sequence of array capacities are 0, 4, 8, 16, 25, . . . ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:10.547659Z",
     "start_time": "2019-07-15T02:05:10.471200Z"
    }
   },
   "outputs": [],
   "source": [
    "def test_array_2(n=27):\n",
    "    data = []\n",
    "    max_size = 0\n",
    "    for _ in range(n):\n",
    "        a = len(data)\n",
    "        b = sys.getsizeof(data)\n",
    "        # 第一次打印\n",
    "        if max_size == 0:\n",
    "            max_size = b\n",
    "        if b > max_size:\n",
    "            print('Length: {0:3d}; Size in bytes: {1:4d}'.format(a-1, max_size))\n",
    "            max_size = b\n",
    "        data.append(None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:10.648895Z",
     "start_time": "2019-07-15T02:05:10.555044Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length:   0; Size in bytes:   64\n",
      "Length:   4; Size in bytes:   96\n",
      "Length:   8; Size in bytes:  128\n",
      "Length:  16; Size in bytes:  192\n",
      "Length:  25; Size in bytes:  264\n"
     ]
    }
   ],
   "source": [
    "test_array_2()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### R-5.3 \n",
    "Modify the experiment from Code Fragment 5.1 in order to demonstrate\n",
    "that Python’s list class occasionally shrinks the size of its underlying array\n",
    "when elements are popped from a list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:10.746795Z",
     "start_time": "2019-07-15T02:05:10.652732Z"
    }
   },
   "outputs": [],
   "source": [
    "def test_array_3(n=27):\n",
    "    data = [None] * n\n",
    "    for _ in range(n):\n",
    "        a = len(data)\n",
    "        b = sys.getsizeof(data)\n",
    "        print('Length: {0:3d}; Size in bytes: {1:4d}'.format(a, b))\n",
    "        data.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:10.843433Z",
     "start_time": "2019-07-15T02:05:10.749831Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length:  27; Size in bytes:  280\n",
      "Length:  26; Size in bytes:  280\n",
      "Length:  25; Size in bytes:  280\n",
      "Length:  24; Size in bytes:  280\n",
      "Length:  23; Size in bytes:  280\n",
      "Length:  22; Size in bytes:  280\n",
      "Length:  21; Size in bytes:  280\n",
      "Length:  20; Size in bytes:  280\n",
      "Length:  19; Size in bytes:  280\n",
      "Length:  18; Size in bytes:  280\n",
      "Length:  17; Size in bytes:  280\n",
      "Length:  16; Size in bytes:  280\n",
      "Length:  15; Size in bytes:  280\n",
      "Length:  14; Size in bytes:  280\n",
      "Length:  13; Size in bytes:  280\n",
      "Length:  12; Size in bytes:  216\n",
      "Length:  11; Size in bytes:  216\n",
      "Length:  10; Size in bytes:  216\n",
      "Length:   9; Size in bytes:  216\n",
      "Length:   8; Size in bytes:  160\n",
      "Length:   7; Size in bytes:  160\n",
      "Length:   6; Size in bytes:  160\n",
      "Length:   5; Size in bytes:  128\n",
      "Length:   4; Size in bytes:  128\n",
      "Length:   3; Size in bytes:  112\n",
      "Length:   2; Size in bytes:  104\n",
      "Length:   1; Size in bytes:   96\n"
     ]
    }
   ],
   "source": [
    "test_array_3()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### R-5.4\n",
    "Our DynamicArray class, as given in Code Fragment 5.3, does not support\n",
    "use of negative indices with getitem . Update that method to better\n",
    "match the semantics of a Python list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:10.950178Z",
     "start_time": "2019-07-15T02:05:10.848616Z"
    }
   },
   "outputs": [],
   "source": [
    "class DynamicArray:\n",
    "    \"\"\"A dynamic array class akin to a simplified Python list\"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"Create an empty array\"\"\"\n",
    "        self._n = 0                                       # count actual elements\n",
    "        self._capacity = 1                                # default array capacity\n",
    "        self._A = self._make_array(self._capacity)        # low-level array\n",
    "    \n",
    "    def __len__(self):\n",
    "        \"\"\"Return number of elements stored in the array\"\"\"\n",
    "        return self._n\n",
    "\n",
    "    def __getitem__(self, k):\n",
    "        \"\"\"Return element at index k\"\"\"\n",
    "        # 添加对负数索引的支持\n",
    "        if k < 0:\n",
    "            k += self._n\n",
    "        # 索引查验\n",
    "        if not 0 <= k <= self._n:\n",
    "            raise IndexError('invalid index')\n",
    "        return self._A[k]\n",
    "\n",
    "    # 为了便于查看\n",
    "    def __repr__(self):\n",
    "        if self._n == 0:\n",
    "            return 'Array[]'\n",
    "        return 'Array[' + ', '.join(str(self._A[i]) for i in range(self._n)) + ']'\n",
    "    def append(self, obj):\n",
    "        \"\"\"Add object to end of array\"\"\"\n",
    "        if self._n == self._capacity:\n",
    "            self._resize(2 * self._capacity)\n",
    "        self._A[self._n] = obj\n",
    "        self._n += 1\n",
    "\n",
    "    def _resize(self, c):\n",
    "        \"\"\"Resize internal array to capacity c.\"\"\"\n",
    "        B = self._make_array(c)\n",
    "        for k in range(self._n):\n",
    "            B[k] = self._A[k]\n",
    "        self._A = B\n",
    "        self._capacity = c\n",
    "\n",
    "    def _make_array(self, c):\n",
    "        \"\"\"Return new array with capacity c\"\"\"\n",
    "        return (c * ctypes.py_object)()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:11.092720Z",
     "start_time": "2019-07-15T02:05:10.955630Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Array[0, 1]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = DynamicArray()\n",
    "arr.append(0)\n",
    "arr.append(1)\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:11.169597Z",
     "start_time": "2019-07-15T02:05:11.095826Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 1)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr[0], arr[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### R-5.6\n",
    "Our implementation of insert for the DynamicArray class, as given in\n",
    "Code Fragment 5.5, has the following inefficiency. In the case when a re-\n",
    "size occurs, the resize operation takes time to copy all the elements from\n",
    "an old array to a new array, and then the subsequent loop in the body of\n",
    "insert shifts many of those elements. Give an improved implementation\n",
    "of the insert method, so that, in the case of a resize, the elements are\n",
    "shifted into their final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:11.256055Z",
     "start_time": "2019-07-15T02:05:11.171653Z"
    }
   },
   "outputs": [],
   "source": [
    "class DynamicArrayInsert(DynamicArray):\n",
    "    \"\"\"A dynamic array class akin to a simplified Python list\"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"Create an empty array\"\"\"\n",
    "        super().__init__()\n",
    "\n",
    "    def insert(self, k, value):\n",
    "        \"\"\"Insert value at index k, shifting subsequent value rightward\"\"\"\n",
    "        if self._n == self._capacity:\n",
    "            B = self._make_array(self._capacity * 2)\n",
    "            for i in range(k):\n",
    "                B[i] = self._A[k]\n",
    "            B[k] = value\n",
    "            for j in range(k+1, self._n+1):\n",
    "                B[j] = self._A[j-1]\n",
    "            self._A = B\n",
    "            self._n += 1\n",
    "            self._capacity *= 2\n",
    "        else:\n",
    "            for i in range(self._n, k, -1):\n",
    "                self._A[i] = self._A[i-1]\n",
    "            self._A[k] = value\n",
    "            self._n += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:11.391539Z",
     "start_time": "2019-07-15T02:05:11.258325Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Array[0, 1]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = DynamicArrayInsert()\n",
    "arr.insert(0, 1)\n",
    "arr.insert(0, 0)\n",
    "arr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### R-5.7\n",
    "Let A be an array of size $n ≥ 2$ containing integers from 1 to n − 1, inclu-\n",
    "sive, with exactly one repeated. Describe a fast algorithm for finding the\n",
    "integer in A that is repeated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:11.466746Z",
     "start_time": "2019-07-15T02:05:11.394894Z"
    }
   },
   "outputs": [],
   "source": [
    "def find_dup(nums):\n",
    "    n = len(nums)\n",
    "    return sum(nums) - n*(n-1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:11.558081Z",
     "start_time": "2019-07-15T02:05:11.472519Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_dup([1, 2, 3, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### R-5.8 \n",
    "Experimentally evaluate the efficiency of the pop method of Python’s list\n",
    "class when using varying indices as a parameter, as we did for insert on\n",
    "page 205. Report your results akin to Table 5.5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:11.643942Z",
     "start_time": "2019-07-15T02:05:11.560919Z"
    }
   },
   "outputs": [],
   "source": [
    "def benchmark(test_func):\n",
    "    insert_df = pd.DataFrame(index=['start', 'middle', 'end'],\n",
    "                        columns=['100', '1000', '10000', '100000'])\n",
    "    insert_df.index.name = 'Time(microseconds)'\n",
    "    for n in list(insert_df.columns):\n",
    "        insert_df[n] = [test_func(int(n), mode) for mode in insert_df.index]\n",
    "    return insert_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:16.000869Z",
     "start_time": "2019-07-15T02:05:11.646014Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>100</th>\n",
       "      <th>1000</th>\n",
       "      <th>10000</th>\n",
       "      <th>100000</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Time(microseconds)</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>start</th>\n",
       "      <td>0.221729</td>\n",
       "      <td>0.432253</td>\n",
       "      <td>3.013754</td>\n",
       "      <td>33.644259</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>middle</th>\n",
       "      <td>0.188351</td>\n",
       "      <td>0.269175</td>\n",
       "      <td>0.768781</td>\n",
       "      <td>7.560563</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>end</th>\n",
       "      <td>0.143051</td>\n",
       "      <td>0.116348</td>\n",
       "      <td>0.123477</td>\n",
       "      <td>0.133860</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                         100      1000     10000     100000\n",
       "Time(microseconds)                                         \n",
       "start               0.221729  0.432253  3.013754  33.644259\n",
       "middle              0.188351  0.269175  0.768781   7.560563\n",
       "end                 0.143051  0.116348  0.123477   0.133860"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# insert测试\n",
    "def insert_average(n, mode='start'):\n",
    "    data = []\n",
    "    start = time()\n",
    "    if mode == 'start':\n",
    "        for _ in range(n):\n",
    "            data.insert(0, None)\n",
    "    elif mode == 'middle':\n",
    "        for _ in range(n):\n",
    "            data.insert(n//2, None)\n",
    "    elif mode == 'end':\n",
    "        for _ in range(n):        \n",
    "            data.insert(n, None)\n",
    "    end = time()\n",
    "    return (end - start) * 1000000 / n\n",
    "\n",
    "benchmark(insert_average)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:19.198453Z",
     "start_time": "2019-07-15T02:05:16.006060Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>100</th>\n",
       "      <th>1000</th>\n",
       "      <th>10000</th>\n",
       "      <th>100000</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Time(microseconds)</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>start</th>\n",
       "      <td>0.166893</td>\n",
       "      <td>0.242710</td>\n",
       "      <td>1.876187</td>\n",
       "      <td>21.675179</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>middle</th>\n",
       "      <td>0.214577</td>\n",
       "      <td>0.255585</td>\n",
       "      <td>0.927758</td>\n",
       "      <td>9.610832</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>end</th>\n",
       "      <td>0.119209</td>\n",
       "      <td>0.114441</td>\n",
       "      <td>0.182676</td>\n",
       "      <td>0.115101</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                         100      1000     10000     100000\n",
       "Time(microseconds)                                         \n",
       "start               0.166893  0.242710  1.876187  21.675179\n",
       "middle              0.214577  0.255585  0.927758   9.610832\n",
       "end                 0.119209  0.114441  0.182676   0.115101"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# pop测试\n",
    "def pop_average(n, mode='start'):\n",
    "    data = [None] * n\n",
    "    start = time()\n",
    "    if mode == 'start':\n",
    "        for _ in range(n):\n",
    "            data.pop(0)\n",
    "    elif mode == 'middle':\n",
    "        count = n\n",
    "        while count > 0:\n",
    "            data.pop(count // 2)\n",
    "            count -= 1\n",
    "    elif mode == 'end':\n",
    "        for _ in range(n):\n",
    "            data.pop(-1)\n",
    "    end = time()\n",
    "    return (end - start) * 1000000 / n\n",
    "\n",
    "benchmark(pop_average)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### R-5.10\n",
    "The constructor for the CaesarCipher class in Code Fragment 5.11 can\n",
    "be implemented with a two-line body by building the forward and back-\n",
    "ward strings using a combination of the join method and an appropriate\n",
    "comprehension syntax. Give such an implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:19.213080Z",
     "start_time": "2019-07-15T02:05:19.206525Z"
    }
   },
   "outputs": [],
   "source": [
    "class CaeserCipher:\n",
    "    def __init__(self, shift):\n",
    "        self._forward  = ''.join(chr((k + shift) % 26 + ord('A')) for k in range(26))\n",
    "        self._backward = ''.join(chr((k - shift) % 26 + ord('A')) for k in range(26))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### R-5.11\n",
    "Use standard control structures to compute the sum of all numbers in an\n",
    "n × n data set, represented as a list of lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:19.292794Z",
     "start_time": "2019-07-15T02:05:19.216446Z"
    }
   },
   "outputs": [],
   "source": [
    "def sum_matrix(matrix: List[List[Num]]) -> Num:\n",
    "    result = 0\n",
    "    for raw in matrix:\n",
    "        for num in raw:\n",
    "            result += num\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:19.383812Z",
     "start_time": "2019-07-15T02:05:19.295023Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_matrix([[1, 2], [3, 4]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### R-5.12\n",
    "Describe how the built-in sum function can be combined with Python’s\n",
    "comprehension syntax to compute the sum of all numbers in an n × n data\n",
    "set, represented as a list of lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:19.514895Z",
     "start_time": "2019-07-15T02:05:19.387965Z"
    }
   },
   "outputs": [],
   "source": [
    "def sum_matrix_plus(matrix: List[List[Num]]) -> Num:\n",
    "    return sum(num for raw in matrix for num in raw)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:19.605472Z",
     "start_time": "2019-07-15T02:05:19.517294Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_matrix([[1, 2], [3, 4]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Creativity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-5.14\n",
    "The shuffle method, supported by the random module, takes a Python\n",
    "list and rearranges it so that every possible ordering is equally likely.\n",
    "Implement your own version of such a function. You may rely on the\n",
    "`randrange(n`) function of the random module, which returns a random\n",
    "number between 0 and `n − 1` inclusive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:19.702174Z",
     "start_time": "2019-07-15T02:05:19.613428Z"
    }
   },
   "outputs": [],
   "source": [
    "def shuffule(nums: List[Num]) -> List[Num]:\n",
    "    return sorted(nums, key=lambda x: random.random())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:19.792689Z",
     "start_time": "2019-07-15T02:05:19.704205Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 7, 4, 0, 6, 5, 3]\n",
      "[0, 1, 3, 2, 5, 7, 4, 6]\n",
      "[1, 3, 4, 0, 6, 7, 2, 5]\n"
     ]
    }
   ],
   "source": [
    "l = list(range(8))\n",
    "print(shuffule(l))\n",
    "print(shuffule(l))\n",
    "print(shuffule(l))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-5.16\n",
    "Implement a pop method for the `DynamicArray` class, given in Code `Frag\n",
    "ment 5.3`, that removes the last element of the array, and that shrinks the\n",
    "capacity, N, of the array by half any time the number of elements in the\n",
    "array goes below N/4."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:19.880746Z",
     "start_time": "2019-07-15T02:05:19.796375Z"
    }
   },
   "outputs": [],
   "source": [
    "class DynamicArrayInsertPop(DynamicArrayInsert):\n",
    "    \"\"\"\n",
    "    Implement a pop method for the DynamicArray class.\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        \"\"\"Create an empty array\"\"\"\n",
    "        super().__init__()\n",
    "\n",
    "    def pop(self):\n",
    "        element = self._A.pop()\n",
    "        if self._n < self._capacity // 4:\n",
    "            self._resize(self._capacity // 2)\n",
    "        return element"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-5.21\n",
    "In Section 5.4.2, we described four different ways to compose a long\n",
    "string: (1) repeated concatenation, (2) appending to a temporary list and\n",
    "then joining, (3) using list comprehension with join, and (4) using genera-\n",
    "tor comprehension with join. Develop an experiment to test the efficiency\n",
    "of all four of these approaches and report your findings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:05:56.959309Z",
     "start_time": "2019-07-15T02:05:56.955169Z"
    }
   },
   "outputs": [],
   "source": [
    "document = 'Hello, World!' * 1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:06:06.903514Z",
     "start_time": "2019-07-15T02:06:06.894067Z"
    }
   },
   "outputs": [],
   "source": [
    "def w1_concatenation():\n",
    "    letters = ''\n",
    "    for c in document:\n",
    "        if c.isalpha():\n",
    "            letters += c\n",
    "    return letters\n",
    "\n",
    "\n",
    "def w2_appending():\n",
    "    temp = []\n",
    "    for c in document:\n",
    "        if c.isalpha():\n",
    "            temp.append(c)\n",
    "    letters = ''.join(temp)\n",
    "    return letters\n",
    "\n",
    "\n",
    "def w3_list_comp():\n",
    "    letters = ''.join([c for c in document if c.isalpha()])\n",
    "    return letters\n",
    "\n",
    "\n",
    "def w4_generator():\n",
    "    letters = ''.join(c for c in document if c.isalpha())\n",
    "    return letters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:06:48.101317Z",
     "start_time": "2019-07-15T02:06:34.068556Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.72 ms ± 51.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit w1_concatenation()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:07:32.065945Z",
     "start_time": "2019-07-15T02:07:19.756656Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.51 ms ± 53.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit w2_appending()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:07:40.912749Z",
     "start_time": "2019-07-15T02:07:32.069578Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.08 ms ± 44.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit w3_list_comp()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:07:52.527873Z",
     "start_time": "2019-07-15T02:07:41.194942Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.39 ms ± 15 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit w4_generator()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看出`list comprehension`是最快的，`generator`次之， 其他两项较慢。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-5.31\n",
    "Describe a way to use recursion to add all the numbers in an n × n data\n",
    "set, represented as a list of lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:09:18.655461Z",
     "start_time": "2019-07-15T02:09:18.645445Z"
    }
   },
   "outputs": [],
   "source": [
    "def binary_sum(S: List[List[float]], start: int, stop: int) -> float:\n",
    "    if start >= stop:\n",
    "        return 0\n",
    "    if start == stop - 1:\n",
    "        return sum(S[start])\n",
    "    else:\n",
    "        mid = (start + stop) // 2\n",
    "        return binary_sum(S, start, mid) + binary_sum(S, mid, stop)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-15T02:09:33.918646Z",
     "start_time": "2019-07-15T02:09:33.909664Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binary_sum([[1, 2], [3, 4]], 0, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "250.433px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
